<?php
/**
 * 上楼梯算法（1-3阶的跨度） 其实就是 利用斐波拉契数列
 *
 * f(n) = f(n-1)+f(n-2)+f(n-3) (n=1时 f(n) =1,n=2 f(n)=3,n=3 f(n)=4 n>3)
 */

function louti($num)
{
    if ($num == 1)
        return 1;
    
    if ($num == 2)
        return 2;
    
    if ($num  == 3)
        return 4;
    
    if ($num >3)
        return louti($num-1) + louti($num-2) + louti($num-3);
}

var_dump(louti(4));

function louti_arr($num)
{
    for($i=1;$i<=$num;$i++)
    {
        if ($i==1)
            $arr[$i] = 1;
        if ($i==2)
            $arr[$i] = 2;
        if ($i==3)
            $arr[$i] = 4;
        if ($i>3)
            $arr[$i] = $arr[$i-1] + $arr[$i-2] + $arr[$i-3];
    }
    
    return $arr;
}
var_dump(louti_arr(15));

/**
 * 还有大于3阶的跨度,上楼梯的延审版
 * 通用公式为
 *
 * 当楼梯总阶s树大于一次的最低跨度m
 * f(s,m) = f(s-1) + f(s-2) + f(s-3) + ··· + f(s-m);
 * 当楼梯总阶s树小于一次的最低跨度m
 * f(m,m) = f(m,m-1) +1;
 * s = 1时，return 1;
 * s = 0时，return 0;
 */

function louti_yanshen($s,$m)
{
    $count = 0;
    if ($s == 0)
        return $count;
    if ($s == 1) {
        $count = 1;
    } else {
        if ($s > $m) {
            for ($i = 1; $i <= $m; $i++) {
                $count += louti_yanshen($s - $i,$m);
            }
        } else {
            $count = louti_yanshen($m,$m-1) + 1;
        }
    }
    
    return $count;
}

var_dump(louti_yanshen(4,3));